home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 13 - 1997 (partial) / 13.04 Apr 97 / DesignPatterns / Patterns.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-06  |  3.6 KB  |  138 lines  |  [TEXT/CWIE]
  1. /*
  2.  *  Design Patterns Example
  3.  *  © 1997 John Schettino, js12@gte.com
  4.  *
  5.  */
  6.  
  7. #include <iostream.h>
  8. #include <string.h>
  9. // Use STL Stacks and Queues based on Vectors
  10. #include <list.h>
  11. #include <stack.h> 
  12.  
  13. // The tree node base class
  14. typedef class TreeNode * TreeNodePtr;
  15. typedef class BinaryTreeNode * BinaryTreeNodePtr;
  16. typedef class TreeNodeIterator * TreeNodeIteratorPtr;
  17.  
  18. class TreeNode {
  19.     friend ostream& operator<< (ostream& os, TreeNode& t);
  20.     friend ostream& operator<< (ostream& os, const TreeNodePtr& t);
  21.     
  22. public:
  23.     virtual const char * output(void) {};
  24.     virtual int compare (const TreeNode& otherNode) {};
  25. };
  26.  
  27. // A simple binary tree
  28. class BinaryTreeNode: public TreeNode {
  29. public:
  30.     BinaryTreeNode(const char *name)
  31.         { _fname = new char[strlen(name)+1];
  32.           strcpy(_fname, name);
  33.           _leftChild = _rightChild = 0; }
  34.     virtual const char* output(void) 
  35.         { return _fname; }
  36.     virtual int compare (const BinaryTreeNode& otherNode) 
  37.         { return strcmp(_fname, otherNode._fname); }
  38.  
  39.     // you should have a destructor
  40.     
  41.     // these accessors are used by the builder and iterator
  42.     void setLeftChild(const BinaryTreeNodePtr l) { _leftChild = l; }
  43.     void setRightChild(const BinaryTreeNodePtr r) { _rightChild = r; }
  44.     BinaryTreeNodePtr leftChild() { return _leftChild; }
  45.     BinaryTreeNodePtr rightChild() { return _rightChild; }
  46. private:
  47.     char *_fname;
  48.     BinaryTreeNodePtr _leftChild;
  49.     BinaryTreeNodePtr _rightChild;
  50. };
  51.  
  52.  
  53. // Tree Node Iterator base class
  54. class TreeNodeIterator {  
  55. public:
  56.     // operators
  57.     virtual TreeNodePtr operator() () {};   // get next node
  58.     virtual TreeNodePtr operator++ (int) {};// get next node
  59.     virtual TreeNodePtr operator* () {};    // get current node
  60.  
  61.     // member fn to return the current node only
  62.     virtual TreeNodePtr current() {};
  63.     
  64.     // member fn to move to the next node
  65.     virtual TreeNodePtr next() {};
  66.     
  67.     // member fn to reset iterator to first node
  68.     virtual void reset() {};
  69. };
  70.  
  71. // Depth-First BinaryTree Node Iterator
  72. class DFTreeNodeIterator : public TreeNodeIterator {  
  73. public:
  74.     DFTreeNodeIterator(BinaryTreeNode &tree);
  75.  
  76.     virtual TreeNodePtr operator() () { return operator++(1); }
  77.     virtual TreeNodePtr operator++ (int);
  78.     virtual TreeNodePtr operator* () { return current(); }
  79.     virtual TreeNodePtr current();
  80.     virtual TreeNodePtr next();
  81.     virtual void reset();
  82. private:
  83.     BinaryTreeNode *_origTree, *_tree;
  84.     // use an STL Stack
  85.     stack<list<BinaryTreeNodePtr> > _pendingNodes;
  86.     void _pushLeft();
  87.     
  88. };
  89.  
  90. // Bredth-First BinaryTree Node Iterator
  91. class BFTreeNodeIterator : public TreeNodeIterator {
  92. public:
  93.     BFTreeNodeIterator(BinaryTreeNode &tree);
  94.  
  95.     virtual TreeNodePtr operator() () { return operator++(1); }
  96.     virtual TreeNodePtr operator++ (int);
  97.     virtual TreeNodePtr operator* () { return current(); }
  98.     virtual TreeNodePtr current();
  99.     virtual TreeNodePtr next();
  100.     virtual void reset();
  101. private:
  102.     BinaryTreeNode *_origTree, *_tree;
  103.     // use an STL queue
  104.     queue<list<BinaryTreeNodePtr> > _pendingNodes;
  105.     enum {IO_node, IO_left, IO_right} _current;    
  106. };
  107.  
  108. // Builder for making trees - base class
  109. class TreeBuilder {
  110. public:
  111.     virtual void AddNode(TreeNodePtr theNode) {}
  112.     virtual TreeNodePtr GetTree() { return 0; }
  113. protected:
  114.     TreeBuilder() {};
  115. };
  116.  
  117. // Builder for making binary trees
  118. class BinaryTreeBuilder : public TreeBuilder {
  119. public:
  120.     BinaryTreeBuilder();
  121.     virtual void AddNode(TreeNodePtr theNode);
  122.     virtual TreeNodePtr GetTree();
  123. private:
  124.     TreeNodePtr _currentBTree;
  125. };
  126.  
  127. // Builder for making height-balanced binary trees
  128. class HBTreeBuilder : public TreeBuilder {
  129. public:
  130.     HBTreeBuilder();
  131.     virtual void AddNode(TreeNodePtr theNode);
  132.     virtual TreeNodePtr GetTree();
  133. private:
  134.     TreeNodePtr _currentBTree;
  135. };
  136.  
  137.  
  138.